Coders and decoders are employed by transmitters and receivers which communicate information over signal channels. For example, radio telephones, MODEMs, and video systems include low rate or high rate coders to generate digital signals for communication through a signal channel and decoders to decode signals received from the signal channel. The signal channel is a twisted wire pair, a cable, air, or the like.
For example, in low-rate speech or video systems, analog signals are converted to a digital data sequence. This original data sequence is encoded to form a message prior to transmission using a forward-error-correcting code, such as a convolutional code. The encoded signal is transmitted through the signal channel.
The receiver receives a data sequence corresponding to the message. The received sequence may have been corrupted by the signal channel. To detect the original data sequence, the receiver includes a decoder which is capable of maximum-likelihood decoding, or a similar decoding operation. A maximum likelihood decoder employs the following equation: EQU P{m.sub.i }p.sub.n (.rho.-s.sub.i), (1)
where
P{m.sub.i } is the a priori probability of the entire message mi having been transmitted;
p.sub.n ( ) is the multidimensional probability density function of the additive noise from the channel,
.rho. is the received signal sequence, and
s.sub.i is a possible transmitted signal sequence. The decoder selects the message m.sub.i which maximizes equation 1 (i.e., has the highest probability).
It is further known that in the case of additive white Gaussian noise with a variance .sigma..sup.2, the receiver should find the message that minimizes: EQU (.rho.-s.sub.i).sup.2 -2.sigma..sup.2 1nP{m.sub.i } (2)
The first term, (.rho.-s.sub.i).sup.2, is the squared Euclidean distance in the signal constellation between the received signal sequence .rho. and a possible signal sequence s.sub.i. The second term, 2.rho..sup.2 1nP{m.sub.i }, takes into consideration the a priori probability of the transmitted message. Receivers that select the message m.sub.i that minimizes equation 2 are called maximum a posterior probability (MAP) receivers.
Although these two equations are widely utilized, there are difficulties in implementing each of them. The a priori code word probabilities are not known precisely at the decoder, making optimum decoding impossible. Furthermore, if messages are equally likely, the second term in equation 2 has no bearing on the decision, and therefor can be omitted, resulting in a maximum likelihood (ML) receiver wherein the variance of the noise and the a priori probabilities of the messages are not considered.
ML decoding is typically implemented in practice using, for example, Viterbi decoding in the case of convolution codes. Viterbi decoders of convolution codes perform error correction on demodulated data by searching for the best path through a "trellis". A section of the trellis is illustrated in FIG. 11. In FIG. 11, the trellis decoder will select path 00 or 10 at point A based upon a "metric" generated from the squared Euclidean distance between the received data sequence and a possible encoded sequence terminating at point A with the last coded bits being either 00 or 10. The metric is calculated as a function of the sum of squared Euclidean distances for previous branches on surviving paths through the trellis plus a metric for the path terminating at that point. The path (00 or 10) having the best metric is selected, and the metric for the best pth is stored. The trellis decoder also selects from paths 11 and 01 for point B using the squared Euclidean distances and the metrics for paths ending at point B. The trellis decoder eliminates the path having the worst metric, and stores the metric associated with the best path. The trellis decoder then repeats the path selection operation for each of the points C and D on the trellis. The metrics are stored for the selected path to each of these points. The Viterbi decoder in this manner performs an add-compare-select (ACS) function at each point in the trellis. The process is repeated until all the points of the trellis frame are processed, and the best path through the trellis frame is selected from the stored metrics.
A prior art decoder has been proposed that uses frame-to-frame correlation of speech code parameters to decode speech signals. This decoder looks at a multi-bit parameter and makes a single path selection decision after evaluating the relationship between a possible parameter value X in a current frame and each of the values Y that the parameter may have had in a previous frame. Thus, for a parameter having five binary bits, the decoder selects one of 32 possible paths between the 32 possible values in a previous frame and a possible value X in a current frame. A single path to a possible value X is selected by considering the probability that the parameter will have this current value X if the previous value was Y for Y having each of the 32 possible previous values Y. This decoder employs a correlation memory, storing thirty-two probability values P{X/Y} for this current value X, to make the selection. Each probability value P{X/Y} is the probability that the parameter has value X in a current frame if the parameter had value Y in a previous frame. Because there are 32 possible values X for the five binary bit parameter, and 32 possible values Y for each possible value X, the correlation memory must store a 32 by 32 correlation metric matrix for this one parameter. Other parameters will require additional respective, large, metric memories. The resulting parameter-wise decoder using frame-to-frame parameter correlation values is thus very complex to implement.
Accordingly, it is desirable to provide a decoder with improved operating characteristics which does not require a highly complex decoding operation.